#include"sort.h"

void Print(int* arr,int sz) {
	
	for (size_t i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void Swap(int* x, int* y) {
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void BubbleSort(int* arr, int n) {
	for (int i = 0; i < n - 1; i++) {
		int flag = 0;
		for (int j = 0; j < n - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				Swap(&arr[j], &arr[j + 1]);
				flag = -1;
			}
		}
		if (flag == 0) break;
	}
}


void ShellSort(int* arr, int n) {
	int gap = n;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++) {
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0) {
				if (tmp < arr[end]) {
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
					break;
			}
			arr[end + gap] = tmp;
		}
	}
}

void SelectSort(int* arr, int n) {
	int begin = 0, end = n - 1;
	while (begin < end) {
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++) {
			if (arr[i] > arr[maxi]) maxi = i;
			if (arr[i] < arr[mini]) mini = i;
		}
		if (maxi == begin) maxi = mini;
		Swap(&arr[maxi], &arr[begin]);
		Swap(&arr[mini], &arr[end]);
		begin++;
		end--;
	}
}

void InsertSort(int* arr, int n) {
	for (int i = 0; i < n - 1; i++) {
		int end = i;
		int tmp = arr[i + 1];
		while (end >= 0) {
			if (tmp < arr[end]) {
				arr[end + 1] = arr[end];
				end--;
			}
			else break;
		}
		arr[end+1] = tmp;
	}
}
int _QuickSort(int* arr, int left, int right)
{
	int keyi = left;
	++left;

	while (left <= right)//left和right相遇的位置的值比基准值要大
	{
		while (left <= right && arr[right] > arr[keyi])
		{
			right--;
		}
		//right找到比基准值小/  等于？
		while (left <= right && arr[left] < arr[keyi])
		{
			left++;
		}
		//right left
		if (left <= right)
		{
			Swap(&arr[left++], &arr[right--]);
		}
	}
	//right keyi交换
	Swap(&arr[keyi], &arr[right]);

	return right;
}

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//[left,right]--->找基准值mid
	int keyi = _QuickSort(arr, left, right);
	//左子序列：[left,keyi-1]
	QuickSort(arr, left, keyi - 1);
	//右子序列：[keyi+1,right]
	QuickSort(arr, keyi + 1, right);
}